package com.leetcode.practice.questionface;

import java.util.ArrayList;

import com.leetcode.practice.interfaces.IQuestion;

/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

 

	示例:
	
	现有矩阵 matrix 如下：
	
	[
	  [1,   4,  7, 11, 15],
	  [2,   5,  8, 12, 19],
	  [3,   6,  9, 16, 22],
	  [10, 13, 14, 17, 24],
	  [18, 21, 23, 26, 30]
	]
	给定 target = 5，返回 true。
	
	给定 target = 20，返回 false。
	
	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 * @author Administrator
 *
 */
public class qf3_二维数组查找  implements IQuestion{

	int[][] array= {
			  {1,   4,  7, 11, 15},
			  {2,   5,  8, 12, 19},
			  {3,   6,  9, 16, 22},
			  {10, 13, 14, 17, 24},
			  {18, 21, 23, 26, 30}
	};
	int target=5;
	@Override
	public void solution() {
		// TODO Auto-generated method stub
		solution1();
	}
	
	    static class ListNode {
		        int val;
		        ListNode next = null;
		
		        ListNode(int val) {
		            this.val = val;
		        }
		    }
	    
	  public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
	        ArrayList<Integer> list=new ArrayList();
	        while(listNode!=null){
	            list = addFirst(list,listNode.val);
	            listNode=listNode.next;
	        }
	        return list;
	    }
	    
	    private ArrayList<Integer> addFirst(ArrayList<Integer> list,int i){
	        ArrayList<Integer> newList=new ArrayList(list.size()+1);
	        System.arraycopy(list,0,newList,1,list.size());
	        newList.add(0,i);
	        return newList;
	    }

	private void solution1() {
		boolean isExist=false;
		for(int i=0;i<array.length;i++) {
			for(int j=0;j<array[i].length;j++) {
				if(array[i][j]==target) {
					isExist=true;
				}
			}
		}
		System.out.println(target+"是否存在->"+isExist);
	}
	
	private void solution2() {
		boolean isExist=false;
		int i=0,j=0;
		while(true) {
			if(target==array[i][j]) {
				isExist=true;
				break;
			}else {
				
			}
		}
	}
	
	public static void main(String[] args) {
		qf3_二维数组查找 qf3=new qf3_二维数组查找();
		qf3.solution();
		
		ListNode l1=new ListNode(1);
		ListNode l2=new ListNode(2);
		ListNode l3=new ListNode(3);
		ListNode l4=new ListNode(4);
		l1.next=l2;
		l2.next=l3;
		l3.next=l4;
		ArrayList<Integer> aa=qf3.printListFromTailToHead(l1);
		for(int a:aa) {
			System.out.println("a->"+a);
		}
	}

}
